Блоком строки S в
позиции i назовём наибольшую
подстроку S, которая начинается в позиции i
и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.
Вычислить длину наибольшего блока
заданной строки S.
Вход. Единственная строка S (|S| ≤ 106).
Выход. Длина наибольшего блока строки
S.
Пример входа
abaabaab
Пример выхода
5
строки – z-функция
Построим для строки S в массиве v
z-функцию. Найдем и выведем длину ее наибольшего блока.
Входная строка s содержит не более 1000000 символов. z-функцию строки s сохраняем в векторе v.
vector<int> v;
char s[1000010];
Функция z строит и возвращает z-функцию
для строки s.
vector<int> z(char *s)
{
int i, l, r;
vector<int>
z(len, 0);
for (i = 1, l
= 0, r = 0; i < len; i++)
{
if (i <=
r) z[i] = min (r - i + 1, z[i - l]);
while (i +
z[i] < len && s[z[i]] == s[i + z[i]]) z[i]++;
if (i +
z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
return z;
}
Читаем входную строку s, вычисляем ее длину len. Строим z-функцию при помощи функции
z. Находим длину res наибольшего
блока строки s и выводим ее.
gets(s); len =
strlen(s);
v = z(s); res =
0;
for(i = 1; i < len; i++)
if (res <
v[i]) res = v[i];
printf("%d\n",res);